package com.easy.leetcode;

import java.util.*;

/**
 * 51. N 皇后
 */
public class SolveNQueens51 {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res =new ArrayList<>();
        char[][]path = new char[n][n];
        backTracking(path,0,n,res);
        return res;
    }
    public void backTracking(char[][]path,int row,int n, List<List<String>> res) {
        //结束条件
        if (row==n){
            res.add(path(path));
            return;
        }
        for (int col = 0; col < n; col++) {
            //判断行列上是否合适
            if (check(path,col,row)){
                //放置皇后，
                path[row][col]='Q';
                //判断下一行
                backTracking(path,row+1,n,res);
                //撤掉皇后
                path[row][col]='.';
            }
        }
    }
    //校验行列上放置皇后是否符合条件
    private boolean check(char[][]path,int col,int row){
        //判断列
        for (int i = 0; i <row ; i++) {
            if (path[i][col]=='Q') {
                return false;
            }
        }
        //判断左上
        for (int i = row-1,j=col-1; i >=0 && j>=0 ; i--,j--) {
            if (path[i][j]=='Q') {
                return false;
            }
        }
        //判断右上
        for (int i = row-1,j=col+1; i >=0 && j<path.length ; i--,j++) {
            if (path[i][j]=='Q') {
                return false;
            }
        }
        return true;
    }

    //生成结果
    private List<String> path(char[][] path ){
        List<String> lst= new ArrayList<>();
        for (int i = 0; i < path.length; i++) {
            StringBuffer sb =new StringBuffer();
            for (int j = 0; j < path.length; j++) {
                if (path[i][j]=='Q'){
                    sb.append("Q");
                }else {
                    sb.append(".");
                }
            }
            lst.add(sb.toString());
        }
        return lst;
    }

    public static void main(String[] args) {
        SolveNQueens51 solveNQueens51 = new SolveNQueens51();
        solveNQueens51.solveNQueens(4);
    }

}
